
\documentclass[a4paper, 10pt]{article}
\usepackage[dvips]{color}
\usepackage{bibentry}
\nobibliography*

\topmargin-2.0cm

\advance\oddsidemargin-0.65in

\textheight9.2in \textwidth6.75in

\textheight9.2in \textwidth6.75in
\newcommand\bb[1]{\mbox{\em #1}}
\newcommand{\todo}[1]{\bf[[#1]]}

\newcommand{\clz}[1]{{\color{red}\todo{@clz: #1}}}
\newcommand{\note}[1]{{\color{magenta}\todo{todo: #1}}}
\newcommand{\CodeIn}[1]{{\small\texttt{#1}}}
\def\baselinestretch{1.05}
\begin{document}

\tableofcontents
\section{to read}
Dual decomposition and its applications; M Collins,  A Mccallum

\note{Discriminatively Trained Mixtures of Deformable Part Models}

\note{strong negative}
\section{Introduction}
\subsection{Discriminative Method for HMM, Michael Collins
~\cite{collins02}}
\begin{itemize}
\item Voted Perceptron algorithm for CRF and exponential family;
\item     Proof, the error is bounded by $\frac{R^2}{\delta^2}$, where $R$ is
$\|\phi(x,z)-\phi(x,y)\|$, and $\delta$ is its separationability.
\end{itemize}

\subsection{Dual Decomposition}
The videolecture is about decoding trees and the tutorial paper
is~\cite{SonGloJaa_optbook}
\begin{itemize}
\item There are two problems on hand, each of the MAP inference is easy to solve
individually,i.e. $y=\arg\max_y f(y)$ and $z=\arg\max_z g(z)$
\item There are some constraints about $y$ and $z$, e.g. the
dependency parse of MST and sibling model must agree on each other.
\item Do inference on
\[\arg\max_{y,z}f(x)+g(z)\ while\ \ y=z\]
\end{itemize}

The motivated parsing + tagging example by M Collins:
\begin{eqnarray}
&y^{(k)} \leftarrow \arg\max_{y \in \mathcal{Y}} \left(f(y) + \sum_{i,t} u^{(k-1)}(i,t)y(i,t)\right)\\
&z^{(k)} \leftarrow \arg\max_{z \in \mathcal{Z}} \left(g(z) - \sum_{i,t} u^{(k-1)}(i,t)z(i,t)\right)\\
&\forall i,t:\ y^{k}(i,t)=z^{k}(i,t) \Rightarrow Finish\\
&o.w.\ u^{(k+1)}(i,t) \leftarrow u^{(k)}(i,t) - \delta_k (y^{(k)}(i,t)-z^{(k)}(i,t))
\end{eqnarray}

Other applications:
\begin{itemize}
\item combined constituency and dependency parsing;
\item MAP problem for pairwise Markov random fields (grid); two tree inference
\item traveling salesman problem: inference algorithm is 1-tree; maximum spanning tree; greedy add 1 to the tree;
the constraint is that every node must have 2 incident edges.
\[L(u,y) = \sum_{e\in E} y_e \theta_e + \sum_{i=1}^n u_i (\sum y_e -2)\]
\item phrase-based translation: constraints is every word must translated at least and at most once in translation. The relaxed opt problem is, the total number of
source word translated is $N$.
\end{itemize}

\section{Applications}
\subsection{WebTables: Exploring the Power of Tables on the Web
\cite{Cafarella:2008}}
\begin{itemize}
\item {\bf extract relations} by hand written detectors and
statistically-trained classifiers
\item \textbf{Attribute Correlation Statistics} (ACSDb): frequency count that
indicates how many relations express that schema.
\item \textbf{featureRank} for relation; see Table 2.
\item \textbf{schemaRank} ACSDb-based schema coherency score; Pointwise
Mutual Information; how strongly two items are related
\[pmi(a,b)=\log \left\{\frac{p(a,b)}{p(a)p(b)}\right\}\]
\item \textbf{index}: two dimensional offset
\item \textbf{schema auto-complete} by ACSDb: maximizes $p(S-I|I)$.
\item \textbf{attribute synonym-finding}: not in the same schema $p(a,b)=0$ and
\[syn(a,b)=\frac{p(a)p(b)}{\epsilon + \sum_{z\in
A}(p(z|a,C)-p(z|b,C))^2}\]
\item similarity schema in the graph by {\bf neighbor similarity}:
\[neighborSim(X,Y,D)=\frac{1}{|X||Y|} \sum_{a\in X,b\in Y}\log(\frac{p(a,b|D)}{p(a|D)p(b|D)})\]
\end{itemize}

\section{Skill}
\subsection{Heuristic}
Pointwise Mutual Information: how strongly two items are related.
\[pmi(a,b)=\log \left\{\frac{p(a,b)}{p(a)p(b)}\right\}\]

Greedy auto-complete \[p(S-I|I)\]

synonym-finding
\[syn(a,b)=\frac{p(a)p(b)}{\epsilon + \sum_{z\in
A}(p(z|a,C)-p(z|b,C))^2}\]

neighbor similarity:
\[neighborSim(X,Y,D)=\frac{1}{|X||Y|} \sum_{a\in X,b\in Y}\log(\frac{p(a,b|D)}{p(a|D)p(b|D)})\]

\section{phrases}
of particular value

pairwise interaction,  triplet interaction; a given triplet (triple) $\{s,t,u\}$; 3-tuple=triplet=triple

one major problem is determining the value $\alpha^*$ at which this ensemble is conjectured to undergo a phase transition from being satisfiable to being unsatisfiable.

... is referred to as ...




\bibliographystyle{alpha}
\bibliography{acl11}

\end{document}
